package com.leetcode.search.dfs;

/**
 * @author Dennis Li
 * @date 2020/7/26 15:40
 */
public class FindCircleNum_547 {

    // 晚上研究这道题用并查集怎么写
    private int n;

    public int findCircleNum(int[][] M) {
        n = M.length;
        if (n == 0) return 0;
        // 查看某人是否已经被访问过，如果被访问过说明在一个社交圈
        boolean[] visited = new boolean[n];
        int circleNum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[j]) {
                    dfs(M, j, visited);
                    circleNum++;
                }
            }
        }
        return circleNum;
    }

    private void dfs(int[][] M, int i, boolean[] visited) {
        if (visited[i]) return;
        visited[i] = true;
        // 只需要遍历这一个人的朋友圈 -- 即矩阵中的这一行
        for (int j = 0; j < n; j++) {
            if (M[i][j] == 1 && !visited[j])
                dfs(M, j, visited);
        }
    }

    static class Solution {

        private int find(int[] nums, int i) {
            return nums[i] == i ? i : (nums[i] = find(nums, nums[i]));
        }

        private void union(int[] nums, int x, int y) {
            int f1 = find(nums, x);
            int f2 = find(nums, y);

            if (f1 != f2) {
                nums[f2] = f1;
            }
        }

        public int findCircleNum(int[][] M) {
            int people = M.length;

            int[] relations = new int[people];

            for (int i = 0; i < people; i++) {
                relations[i] = i;
            }

            for (int i = 0; i < people; i++) {
                for (int j = 0; j < people; j++) {
                    if (i != j && M[i][j] == 1)
                        union(relations, i, j);
                }
            }

            int count = 0;
            // 并查集的判断方式，不是判断不相同的有多少个，而是判断是否和原来的自己相等
            for (int i = 0; i < people; i++) {
                if (relations[i] == i)
                    count++;
            }

            return count;
        }
    }


}
